import java.util.Arrays;
import java.util.Stack;

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}


public class Test {


    public ListNode reverseList(ListNode head) {
        ListNode cur = head.next;
        ListNode curA = cur.next;
        while (cur != null) {
            cur = curA.next;
            curA = head;
            head = curA;
            curA = cur;

        }
        head.next = null;
        return head;
    }


    public ListNode middleNode(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }


    /*public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null && list2 == null) {
            return null;
        }
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        ListNode a1 = list1;
        ListNode b1 = a1.next;
        ListNode a2 = list2;
        ListNode b2 = a2.next;
        while (b1 == null && b2 == null) {
            if ((b1 == null && b2 == null) && a1.val <= a2.val) {
                a1.next = a2;
                a1 = b1;
                b1 = b1.next;
                list2 = a1;
            }
            if ((b1 == null && b2 == null) && a1.val >= a2.val) {
                a2.next = a1;
                a2 = b2;
                b2 = b2.next;
                list2 = a2;
            }
        }
        if (a2 == null) {
            return list1;
        } else {
            list2.next = a2;
        }

        return list1;

    }*/


    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        ListNode head = new ListNode();
        ListNode cur = head;

        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                cur.next = list1;
                cur = list1;
                list1 = list1.next;
            } else {
                cur.next = list2;
                cur = list2;
                list2 = list2.next;
            }
        }
        while (list2 != null) {
            cur.next = list2;
            cur = list2;
            list2 = list2.next;
        }
        while (list1 != null) {
            cur.next = list1;
            cur = list1;
            list1 = list1.next;
        }
        return head;
    }

    public ListNode partition(ListNode head, int x) {
        if (head == null) {
            return null;
        }
        ListNode dummy1 = new ListNode(0); // 小于x的节点
        ListNode dummy2 = new ListNode(0); // 大于等于x的节点
        ListNode p1 = dummy1;
        ListNode p2 = dummy2;

        while (head != null) {
            if (head.val < x) {
                p1.next = head;
                p1 = head;
            } else {
                p2.next = head;
                p2 = head;
            }
            head = head.next;
        }

        p1.next = p2.next;
        return dummy1.next;
    }


    public ListNode detectCycle(ListNode head) {
        if (head == null) return null;
        ListNode fast = head;
        ListNode slow = head;
        while (fast != slow && fast != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        if (fast == null && slow == null) {
            return null;
        }
        slow = head;
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }

    public boolean isValid(String s) {
        if (s == null) {
            return false;
        }
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == '(' || ch == '{' || ch == '[') {
                stack.push(ch);
            }else{
                if(stack.isEmpty()){
                    return false;
                }
                char top = stack.peek();
                if (ch == ')' && top == '(' ||
                        ch == '}' && top == '{' ||
                        ch == ']' && top == '[') {
                    stack.pop();
                } else {
                    return false;
                }
            }

        }
        if (!stack.empty()) {
            return false;
        }
        return true;

    }

}
